home *** CD-ROM | disk | FTP | other *** search
/ Aminet 32 / Aminet 32 (1999)(Schatztruhe)[!][Aug 1999].iso / Aminet / dev / lang / Python151_Src.lha / Python1.5_Source / Modules / regexpr.c < prev    next >
C/C++ Source or Header  |  1998-05-26  |  47KB  |  2,138 lines
  1. /* regexpr.c
  2.  *
  3.  * Author: Tatu Ylonen <ylo@ngs.fi>
  4.  *
  5.  * Copyright (c) 1991 Tatu Ylonen, Espoo, Finland
  6.  *
  7.  * Permission to use, copy, modify, distribute, and sell this software
  8.  * and its documentation for any purpose is hereby granted without
  9.  * fee, provided that the above copyright notice appear in all copies.
  10.  * This software is provided "as is" without express or implied
  11.  * warranty.
  12.  *
  13.  * Created: Thu Sep 26 17:14:05 1991 ylo
  14.  * Last modified: Mon Nov  4 17:06:48 1991 ylo
  15.  * Ported to Think C: 19 Jan 1992 guido@cwi.nl
  16.  *
  17.  * This code draws many ideas from the regular expression packages by
  18.  * Henry Spencer of the University of Toronto and Richard Stallman of
  19.  * the Free Software Foundation.
  20.  *
  21.  * Emacs-specific code and syntax table code is almost directly borrowed
  22.  * from GNU regexp.
  23.  *
  24.  * Bugs fixed and lots of reorganization by Jeffrey C. Ollie, April
  25.  * 1997 Thanks for bug reports and ideas from Andrew Kuchling, Tim
  26.  * Peters, Guido van Rossum, Ka-Ping Yee, Sjoerd Mullender, and
  27.  * probably one or two others that I'm forgetting.
  28.  *
  29.  * $Id: regexpr.c,v 1.28 1998/04/10 22:27:39 guido Exp $ */
  30.  
  31. #include "Python.h"
  32. #include "regexpr.h"
  33. #include <assert.h>
  34.  
  35. #include "protos/regexpr_protos.h"
  36.  
  37. /* The original code blithely assumed that sizeof(short) == 2.  Not
  38.  * always true.  Original instances of "(short)x" were replaced by
  39.  * SHORT(x), where SHORT is #defined below.  */
  40.  
  41. #define SHORT(x) ((x) & 0x8000 ? (x) - 0x10000 : (x))
  42.  
  43. /* The stack implementation is taken from an idea by Andrew Kuchling.
  44.  * It's a doubly linked list of arrays. The advantages of this over a
  45.  * simple linked list are that the number of mallocs required are
  46.  * reduced. It also makes it possible to statically allocate enough
  47.  * space so that small patterns don't ever need to call malloc.
  48.  *
  49.  * The advantages over a single array is that is periodically
  50.  * realloced when more space is needed is that we avoid ever copying
  51.  * the stack. */
  52.  
  53. /* item_t is the basic stack element.  Defined as a union of
  54.  * structures so that both registers, failure points, and counters can
  55.  * be pushed/popped from the stack.  There's nothing built into the
  56.  * item to keep track of whether a certain stack item is a register, a
  57.  * failure point, or a counter. */
  58.  
  59. typedef union item_t
  60. {
  61.     struct
  62.     {
  63.         int num;
  64.         int level;
  65.         unsigned char *start;
  66.         unsigned char *end;
  67.     } reg;
  68.     struct
  69.     {
  70.         int count;
  71.         int level;
  72.         int phantom;
  73.         unsigned char *code;
  74.         unsigned char *text;
  75.     } fail;
  76.     struct
  77.     {
  78.         int num;
  79.         int level;
  80.         int count;
  81.     } cntr;
  82. } item_t;
  83.  
  84. #define STACK_PAGE_SIZE 256
  85. #define NUM_REGISTERS 256
  86.  
  87. /* A 'page' of stack items. */
  88.  
  89. typedef struct item_page_t
  90. {
  91.     item_t items[STACK_PAGE_SIZE];
  92.     struct item_page_t *prev;
  93.     struct item_page_t *next;
  94. } item_page_t;
  95.  
  96.  
  97. typedef struct match_state
  98. {
  99.     /* The number of registers that have been pushed onto the stack
  100.      * since the last failure point. */
  101.  
  102.     int count;
  103.  
  104.     /* Used to control when registers need to be pushed onto the
  105.      * stack. */
  106.     
  107.     int level;
  108.     
  109.     /* The number of failure points on the stack. */
  110.     
  111.     int point;
  112.     
  113.     /* Storage for the registers.  Each register consists of two
  114.      * pointers to characters.  So register N is represented as
  115.      * start[N] and end[N].  The pointers must be converted to
  116.      * offsets from the beginning of the string before returning the
  117.      * registers to the calling program. */
  118.     
  119.     unsigned char *start[NUM_REGISTERS];
  120.     unsigned char *end[NUM_REGISTERS];
  121.     
  122.     /* Keeps track of whether a register has changed recently. */
  123.     
  124.     int changed[NUM_REGISTERS];
  125.     
  126.     /* Structure to encapsulate the stack. */
  127.     struct
  128.     {
  129.         /* index into the curent page.  If index == 0 and you need
  130.          * to pop an item, move to the previous page and set index
  131.          * = STACK_PAGE_SIZE - 1.  Otherwise decrement index to
  132.          * push a page. If index == STACK_PAGE_SIZE and you need
  133.          * to push a page move to the next page and set index =
  134.          * 0. If there is no new next page, allocate a new page
  135.          * and link it in. Otherwise, increment index to push a
  136.          * page. */
  137.         
  138.         int index;
  139.         item_page_t *current; /* Pointer to the current page. */
  140.         item_page_t first; /* First page is statically allocated. */
  141.     } stack;
  142. } match_state;
  143.  
  144. /* Initialize a state object */
  145.  
  146. /* #define NEW_STATE(state) \ */
  147. /* memset(&state, 0, (void *)(&state.stack) - (void *)(&state)); \ */
  148. /* state.stack.current = &state.stack.first; \ */
  149. /* state.stack.first.prev = NULL; \ */
  150. /* state.stack.first.next = NULL; \ */
  151. /* state.stack.index = 0; \ */
  152. /* state.level = 1 */
  153.  
  154. #define NEW_STATE(state, nregs) \
  155. { \
  156.     int i; \
  157.     for (i = 0; i < nregs; i++) \
  158.     { \
  159.         state.start[i] = NULL; \
  160.         state.end[i] = NULL; \
  161.         state.changed[i] = 0; \
  162.     } \
  163.     state.stack.current = &state.stack.first; \
  164.     state.stack.first.prev = NULL; \
  165.     state.stack.first.next = NULL; \
  166.     state.stack.index = 0; \
  167.     state.level = 1; \
  168.     state.count = 0; \
  169.     state.level = 0; \
  170.     state.point = 0; \
  171. }
  172.  
  173. /* Free any memory that might have been malloc'd */
  174.  
  175. #define FREE_STATE(state) \
  176. while(state.stack.first.next != NULL) \
  177. { \
  178.     state.stack.current = state.stack.first.next; \
  179.     state.stack.first.next = state.stack.current->next; \
  180.     free(state.stack.current); \
  181. }
  182.  
  183. /* Discard the top 'count' stack items. */
  184.  
  185. #define STACK_DISCARD(stack, count, on_error) \
  186. stack.index -= count; \
  187. while (stack.index < 0) \
  188. { \
  189.     if (stack.current->prev == NULL) \
  190.         on_error; \
  191.     stack.current = stack.current->prev; \
  192.     stack.index += STACK_PAGE_SIZE; \
  193. }
  194.  
  195. /* Store a pointer to the previous item on the stack. Used to pop an
  196.  * item off of the stack. */
  197.  
  198. #define STACK_PREV(stack, top, on_error) \
  199. if (stack.index == 0) \
  200. { \
  201.     if (stack.current->prev == NULL) \
  202.         on_error; \
  203.     stack.current = stack.current->prev; \
  204.     stack.index = STACK_PAGE_SIZE - 1; \
  205. } \
  206. else \
  207. { \
  208.     stack.index--; \
  209. } \
  210. top = &(stack.current->items[stack.index])
  211.  
  212. /* Store a pointer to the next item on the stack. Used to push an item
  213.  * on to the stack. */
  214.  
  215. #define STACK_NEXT(stack, top, on_error) \
  216. if (stack.index == STACK_PAGE_SIZE) \
  217. { \
  218.     if (stack.current->next == NULL) \
  219.     { \
  220.         stack.current->next = (item_page_t *)malloc(sizeof(item_page_t)); \
  221.         if (stack.current->next == NULL) \
  222.             on_error; \
  223.         stack.current->next->prev = stack.current; \
  224.         stack.current->next->next = NULL; \
  225.     } \
  226.     stack.current = stack.current->next; \
  227.     stack.index = 0; \
  228. } \
  229. top = &(stack.current->items[stack.index++])
  230.  
  231. /* Store a pointer to the item that is 'count' items back in the
  232.  * stack. STACK_BACK(stack, top, 1, on_error) is equivalent to
  233.  * STACK_TOP(stack, top, on_error).  */
  234.  
  235. #define STACK_BACK(stack, top, count, on_error) \
  236. { \
  237.     int index; \
  238.     item_page_t *current; \
  239.     current = stack.current; \
  240.     index = stack.index - (count); \
  241.     while (index < 0) \
  242.     { \
  243.         if (current->prev == NULL) \
  244.             on_error; \
  245.         current = current->prev; \
  246.         index += STACK_PAGE_SIZE; \
  247.     } \
  248.     top = &(current->items[index]); \
  249. }
  250.  
  251. /* Store a pointer to the top item on the stack. Execute the
  252.  * 'on_error' code if there are no items on the stack. */
  253.  
  254. #define STACK_TOP(stack, top, on_error) \
  255. if (stack.index == 0) \
  256. { \
  257.     if (stack.current->prev == NULL) \
  258.         on_error; \
  259.     top = &(stack.current->prev->items[STACK_PAGE_SIZE - 1]); \
  260. } \
  261. else \
  262. { \
  263.     top = &(stack.current->items[stack.index - 1]); \
  264. }
  265.  
  266. /* Test to see if the stack is empty */
  267.  
  268. #define STACK_EMPTY(stack) ((stack.index == 0) && \
  269.                 (stack.current->prev == NULL))
  270.  
  271. /* Return the start of register 'reg' */
  272.  
  273. #define GET_REG_START(state, reg) (state.start[reg])
  274.  
  275. /* Return the end of register 'reg' */
  276.  
  277. #define GET_REG_END(state, reg) (state.end[reg])
  278.  
  279. /* Set the start of register 'reg'. If the state of the register needs
  280.  * saving, push it on the stack. */
  281.  
  282. #define SET_REG_START(state, reg, text, on_error) \
  283. if(state.changed[reg] < state.level) \
  284. { \
  285.     item_t *item; \
  286.     STACK_NEXT(state.stack, item, on_error); \
  287.     item->reg.num = reg; \
  288.     item->reg.start = state.start[reg]; \
  289.     item->reg.end = state.end[reg]; \
  290.     item->reg.level = state.changed[reg]; \
  291.     state.changed[reg] = state.level; \
  292.     state.count++; \
  293. } \
  294. state.start[reg] = text
  295.  
  296. /* Set the end of register 'reg'. If the state of the register needs
  297.  * saving, push it on the stack. */
  298.  
  299. #define SET_REG_END(state, reg, text, on_error) \
  300. if(state.changed[reg] < state.level) \
  301. { \
  302.     item_t *item; \
  303.     STACK_NEXT(state.stack, item, on_error); \
  304.     item->reg.num = reg; \
  305.     item->reg.start = state.start[reg]; \
  306.     item->reg.end = state.end[reg]; \
  307.     item->reg.level = state.changed[reg]; \
  308.     state.changed[reg] = state.level; \
  309.     state.count++; \
  310. } \
  311. state.end[reg] = text
  312.  
  313. #define PUSH_FAILURE(state, xcode, xtext, on_error) \
  314. { \
  315.     item_t *item; \
  316.     STACK_NEXT(state.stack, item, on_error); \
  317.     item->fail.code = xcode; \
  318.     item->fail.text = xtext; \
  319.     item->fail.count = state.count; \
  320.     item->fail.level = state.level; \
  321.     item->fail.phantom = 0; \
  322.     state.count = 0; \
  323.     state.level++; \
  324.     state.point++; \
  325. }
  326.  
  327. /* Update the last failure point with a new position in the text. */
  328.  
  329. #define UPDATE_FAILURE(state, xtext, on_error) \
  330. { \
  331.     item_t *item; \
  332.     STACK_BACK(state.stack, item, state.count + 1, on_error); \
  333.     if (!item->fail.phantom) \
  334.     { \
  335.         item_t *item2; \
  336.         STACK_NEXT(state.stack, item2, on_error); \
  337.         item2->fail.code = item->fail.code; \
  338.         item2->fail.text = xtext; \
  339.         item2->fail.count = state.count; \
  340.         item2->fail.level = state.level; \
  341.         item2->fail.phantom = 1; \
  342.         state.count = 0; \
  343.         state.level++; \
  344.         state.point++; \
  345.     } \
  346.     else \
  347.     { \
  348.         STACK_DISCARD(state.stack, state.count, on_error); \
  349.         STACK_TOP(state.stack, item, on_error); \
  350.         item->fail.text = xtext; \
  351.         state.count = 0; \
  352.         state.level++; \
  353.     } \
  354. }
  355.  
  356. #define POP_FAILURE(state, xcode, xtext, on_empty, on_error) \
  357. { \
  358.     item_t *item; \
  359.     do \
  360.     { \
  361.         while(state.count > 0) \
  362.         { \
  363.             STACK_PREV(state.stack, item, on_error); \
  364.             state.start[item->reg.num] = item->reg.start; \
  365.             state.end[item->reg.num] = item->reg.end; \
  366.             state.changed[item->reg.num] = item->reg.level; \
  367.             state.count--; \
  368.         } \
  369.         STACK_PREV(state.stack, item, on_empty); \
  370.         xcode = item->fail.code; \
  371.         xtext = item->fail.text; \
  372.         state.count = item->fail.count; \
  373.         state.level = item->fail.level; \
  374.         state.point--; \
  375.     } \
  376.     while (item->fail.text == NULL); \
  377. }
  378.  
  379. enum regexp_compiled_ops /* opcodes for compiled regexp */
  380. {
  381.     Cend,              /* end of pattern reached */
  382.     Cbol,              /* beginning of line */
  383.     Ceol,              /* end of line */
  384.     Cset,              /* character set.  Followed by 32 bytes of set. */
  385.     Cexact,              /* followed by a byte to match */
  386.     Canychar,          /* matches any character except newline */
  387.     Cstart_memory,          /* set register start addr (followed by reg number) */
  388.     Cend_memory,          /* set register end addr (followed by reg number) */
  389.     Cmatch_memory,          /* match a duplicate of reg contents (regnum follows)*/
  390.     Cjump,              /* followed by two bytes (lsb,msb) of displacement. */
  391.     Cstar_jump,          /* will change to jump/update_failure_jump at runtime */
  392.     Cfailure_jump,          /* jump to addr on failure */
  393.     Cupdate_failure_jump, /* update topmost failure point and jump */
  394.     Cdummy_failure_jump,  /* push a dummy failure point and jump */
  395.     Cbegbuf,          /* match at beginning of buffer */
  396.     Cendbuf,          /* match at end of buffer */
  397.     Cwordbeg,          /* match at beginning of word */
  398.     Cwordend,          /* match at end of word */
  399.     Cwordbound,          /* match if at word boundary */
  400.     Cnotwordbound,        /* match if not at word boundary */
  401.     Csyntaxspec,          /* matches syntax code (1 byte follows) */
  402.     Cnotsyntaxspec,       /* matches if syntax code does not match (1 byte follows) */
  403.     Crepeat1
  404. };
  405.  
  406. enum regexp_syntax_op    /* syntax codes for plain and quoted characters */
  407. {
  408.     Rend,          /* special code for end of regexp */
  409.     Rnormal,      /* normal character */
  410.     Ranychar,      /* any character except newline */
  411.     Rquote,          /* the quote character */
  412.     Rbol,          /* match beginning of line */
  413.     Reol,          /* match end of line */
  414.     Roptional,      /* match preceding expression optionally */
  415.     Rstar,          /* match preceding expr zero or more times */
  416.     Rplus,          /* match preceding expr one or more times */
  417.     Ror,          /* match either of alternatives */
  418.     Ropenpar,      /* opening parenthesis */
  419.     Rclosepar,      /* closing parenthesis */
  420.     Rmemory,      /* match memory register */
  421.     Rextended_memory, /* \vnn to match registers 10-99 */
  422.     Ropenset,      /* open set.  Internal syntax hard-coded below. */
  423.     /* the following are gnu extensions to "normal" regexp syntax */
  424.     Rbegbuf,      /* beginning of buffer */
  425.     Rendbuf,      /* end of buffer */
  426.     Rwordchar,      /* word character */
  427.     Rnotwordchar,      /* not word character */
  428.     Rwordbeg,      /* beginning of word */
  429.     Rwordend,      /* end of word */
  430.     Rwordbound,      /* word bound */
  431.     Rnotwordbound,      /* not word bound */
  432.     Rnum_ops
  433. };
  434.  
  435. static int re_compile_initialized = 0;
  436. static int regexp_syntax = 0;
  437. int re_syntax = 0; /* Exported copy of regexp_syntax */
  438. static unsigned char regexp_plain_ops[256];
  439. static unsigned char regexp_quoted_ops[256];
  440. static unsigned char regexp_precedences[Rnum_ops];
  441. static int regexp_context_indep_ops;
  442. static int regexp_ansi_sequences;
  443.  
  444. #define NUM_LEVELS  5    /* number of precedence levels in use */
  445. #define MAX_NESTING 100  /* max nesting level of operators */
  446.  
  447. #define SYNTAX(ch) re_syntax_table[(unsigned char)(ch)]
  448.  
  449. unsigned char re_syntax_table[256];
  450.  
  451. void re_compile_initialize()
  452. {
  453.     int a;
  454.   
  455.     static int syntax_table_inited = 0;
  456.  
  457.     if (!syntax_table_inited)
  458.     {
  459.         syntax_table_inited = 1;
  460.         memset(re_syntax_table, 0, 256);
  461.         for (a = 'a'; a <= 'z'; a++)
  462.             re_syntax_table[a] = Sword;
  463.         for (a = 'A'; a <= 'Z'; a++)
  464.             re_syntax_table[a] = Sword;
  465.         for (a = '0'; a <= '9'; a++)
  466.             re_syntax_table[a] = Sword | Sdigit | Shexdigit;
  467.         for (a = '0'; a <= '7'; a++)
  468.             re_syntax_table[a] |= Soctaldigit;
  469.         for (a = 'A'; a <= 'F'; a++)
  470.             re_syntax_table[a] |= Shexdigit;
  471.         for (a = 'a'; a <= 'f'; a++)
  472.             re_syntax_table[a] |= Shexdigit;
  473.         re_syntax_table['_'] = Sword;
  474.         for (a = 9; a <= 13; a++)
  475.             re_syntax_table[a] = Swhitespace;
  476.         re_syntax_table[' '] = Swhitespace;
  477.     }
  478.     re_compile_initialized = 1;
  479.     for (a = 0; a < 256; a++)
  480.     {
  481.         regexp_plain_ops[a] = Rnormal;
  482.         regexp_quoted_ops[a] = Rnormal;
  483.     }
  484.     for (a = '0'; a <= '9'; a++)
  485.         regexp_quoted_ops[a] = Rmemory;
  486.     regexp_plain_ops['\134'] = Rquote;
  487.     if (regexp_syntax & RE_NO_BK_PARENS)
  488.     {
  489.         regexp_plain_ops['('] = Ropenpar;
  490.         regexp_plain_ops[')'] = Rclosepar;
  491.     }
  492.     else
  493.     {
  494.         regexp_quoted_ops['('] = Ropenpar;
  495.         regexp_quoted_ops[')'] = Rclosepar;
  496.     }
  497.     if (regexp_syntax & RE_NO_BK_VBAR)
  498.         regexp_plain_ops['\174'] = Ror;
  499.     else
  500.         regexp_quoted_ops['\174'] = Ror;
  501.     regexp_plain_ops['*'] = Rstar;
  502.     if (regexp_syntax & RE_BK_PLUS_QM)
  503.     {
  504.         regexp_quoted_ops['+'] = Rplus;
  505.         regexp_quoted_ops['?'] = Roptional;
  506.     }
  507.     else
  508.     {
  509.         regexp_plain_ops['+'] = Rplus;
  510.         regexp_plain_ops['?'] = Roptional;
  511.     }
  512.     if (regexp_syntax & RE_NEWLINE_OR)
  513.         regexp_plain_ops['\n'] = Ror;
  514.     regexp_plain_ops['\133'] = Ropenset;
  515.     regexp_plain_ops['\136'] = Rbol;
  516.     regexp_plain_ops['$'] = Reol;
  517.     regexp_plain_ops['.'] = Ranychar;
  518.     if (!(regexp_syntax & RE_NO_GNU_EXTENSIONS))
  519.     {
  520.         regexp_quoted_ops['w'] = Rwordchar;
  521.         regexp_quoted_ops['W'] = Rnotwordchar;
  522.         regexp_quoted_ops['<'] = Rwordbeg;
  523.         regexp_quoted_ops['>'] = Rwordend;
  524.         regexp_quoted_ops['b'] = Rwordbound;
  525.         regexp_quoted_ops['B'] = Rnotwordbound;
  526.         regexp_quoted_ops['`'] = Rbegbuf;
  527.         regexp_quoted_ops['\''] = Rendbuf;
  528.     }
  529.     if (regexp_syntax & RE_ANSI_HEX)
  530.         regexp_quoted_ops['v'] = Rextended_memory;
  531.     for (a = 0; a < Rnum_ops; a++)
  532.         regexp_precedences[a] = 4;
  533.     if (regexp_syntax & RE_TIGHT_VBAR)
  534.     {
  535.         regexp_precedences[Ror] = 3;
  536.         regexp_precedences[Rbol] = 2;
  537.         regexp_precedences[Reol] = 2;
  538.     }
  539.     else
  540.     {
  541.         regexp_precedences[Ror] = 2;
  542.         regexp_precedences[Rbol] = 3;
  543.         regexp_precedences[Reol] = 3;
  544.     }
  545.     regexp_precedences[Rclosepar] = 1;
  546.     regexp_precedences[Rend] = 0;
  547.     regexp_context_indep_ops = (regexp_syntax & RE_CONTEXT_INDEP_OPS) != 0;
  548.     regexp_ansi_sequences = (regexp_syntax & RE_ANSI_HEX) != 0;
  549. }
  550.  
  551. int re_set_syntax(syntax)
  552.     int syntax;
  553. {
  554.     int ret;
  555.     
  556.     ret = regexp_syntax;
  557.     regexp_syntax = syntax;
  558.     re_syntax = syntax; /* Exported copy */
  559.     re_compile_initialize();
  560.     return ret;
  561. }
  562.  
  563. static int hex_char_to_decimal(ch)
  564.     int ch;
  565. {
  566.     if (ch >= '0' && ch <= '9')
  567.         return ch - '0';
  568.     if (ch >= 'a' && ch <= 'f')
  569.         return ch - 'a' + 10;
  570.     if (ch >= 'A' && ch <= 'F')
  571.         return ch - 'A' + 10;
  572.     return 16;
  573. }
  574.  
  575. static void re_compile_fastmap_aux(code,
  576.                    pos,
  577.                    visited,
  578.                    can_be_null,
  579.                    fastmap)
  580.     unsigned char *code;
  581.     int pos;
  582.     unsigned char *visited;
  583.     unsigned char *can_be_null;
  584.     unsigned char *fastmap;
  585. {
  586.     int a;
  587.     int b;
  588.     int syntaxcode;
  589.     
  590.     if (visited[pos])
  591.         return;  /* we have already been here */
  592.     visited[pos] = 1;
  593.     for (;;)
  594.         switch (code[pos++]) {
  595.         case Cend:
  596.             {
  597.                 *can_be_null = 1;
  598.                 return;
  599.             }
  600.         case Cbol:
  601.         case Cbegbuf:
  602.         case Cendbuf:
  603.         case Cwordbeg:
  604.         case Cwordend:
  605.         case Cwordbound:
  606.         case Cnotwordbound:
  607.         {
  608.             for (a = 0; a < 256; a++)
  609.                 fastmap[a] = 1;
  610.             break;
  611.         }
  612.         case Csyntaxspec:
  613.         {
  614.             syntaxcode = code[pos++];
  615.             for (a = 0; a < 256; a++)
  616.                 if (SYNTAX(a) & syntaxcode) 
  617.                     fastmap[a] = 1;
  618.             return;
  619.         }
  620.         case Cnotsyntaxspec:
  621.         {
  622.             syntaxcode = code[pos++];
  623.             for (a = 0; a < 256; a++)
  624.                 if (!(SYNTAX(a) & syntaxcode) )
  625.                     fastmap[a] = 1;
  626.             return;
  627.         }
  628.         case Ceol:
  629.         {
  630.             fastmap['\n'] = 1;
  631.             if (*can_be_null == 0)
  632.                 *can_be_null = 2; /* can match null, but only at end of buffer*/
  633.             return;
  634.         }
  635.         case Cset:
  636.         {
  637.             for (a = 0; a < 256/8; a++)
  638.                 if (code[pos + a] != 0)
  639.                     for (b = 0; b < 8; b++)
  640.                         if (code[pos + a] & (1 << b))
  641.                             fastmap[(a << 3) + b] = 1;
  642.             pos += 256/8;
  643.             return;
  644.         }
  645.         case Cexact:
  646.         {
  647.             fastmap[(unsigned char)code[pos]] = 1;
  648.             return;
  649.         }
  650.         case Canychar:
  651.         {
  652.             for (a = 0; a < 256; a++)
  653.                 if (a != '\n')
  654.                     fastmap[a] = 1;
  655.             return;
  656.         }
  657.         case Cstart_memory:
  658.         case Cend_memory:
  659.         {
  660.             pos++;
  661.             break;
  662.         }
  663.         case Cmatch_memory:
  664.         {
  665.             for (a = 0; a < 256; a++)
  666.                 fastmap[a] = 1;
  667.             *can_be_null = 1;
  668.             return;
  669.         }
  670.         case Cjump:
  671.         case Cdummy_failure_jump:
  672.         case Cupdate_failure_jump:
  673.         case Cstar_jump:
  674.         {
  675.             a = (unsigned char)code[pos++];
  676.             a |= (unsigned char)code[pos++] << 8;
  677.             pos += (int)SHORT(a);
  678.             if (visited[pos])
  679.             {
  680.                 /* argh... the regexp contains empty loops.  This is not
  681.                    good, as this may cause a failure stack overflow when
  682.                    matching.  Oh well. */
  683.                 /* this path leads nowhere; pursue other paths. */
  684.                 return;
  685.             }
  686.             visited[pos] = 1;
  687.             break;
  688.         }
  689.         case Cfailure_jump:
  690.         {
  691.             a = (unsigned char)code[pos++];
  692.             a |= (unsigned char)code[pos++] << 8;
  693.             a = pos + (int)SHORT(a);
  694.             re_compile_fastmap_aux(code, a, visited, can_be_null, fastmap);
  695.             break;
  696.         }
  697.         case Crepeat1:
  698.         {
  699.             pos += 2;
  700.             break;
  701.         }
  702.         default:
  703.         {
  704.                 PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");
  705.                 return;
  706.             /*NOTREACHED*/
  707.         }
  708.         }
  709. }
  710.  
  711. static int re_do_compile_fastmap(buffer,
  712.                  used,
  713.                  pos,
  714.                  can_be_null,
  715.                  fastmap)
  716.     unsigned char *buffer;
  717.     int used;
  718.     int pos;
  719.     unsigned char *can_be_null;
  720.     unsigned char *fastmap;
  721. {
  722.     unsigned char small_visited[512], *visited;
  723.    
  724.     if (used <= sizeof(small_visited))
  725.         visited = small_visited;
  726.     else
  727.     {
  728.         visited = malloc(used);
  729.         if (!visited)
  730.             return 0;
  731.     }
  732.     *can_be_null = 0;
  733.     memset(fastmap, 0, 256);
  734.     memset(visited, 0, used);
  735.     re_compile_fastmap_aux(buffer, pos, visited, can_be_null, fastmap);
  736.     if (visited != small_visited)
  737.         free(visited);
  738.     return 1;
  739. }
  740.  
  741. void re_compile_fastmap(bufp)
  742.     regexp_t bufp;
  743. {
  744.     if (!bufp->fastmap || bufp->fastmap_accurate)
  745.         return;
  746.     assert(bufp->used > 0);
  747.     if (!re_do_compile_fastmap(bufp->buffer,
  748.                    bufp->used,
  749.                    0,
  750.                    &bufp->can_be_null,
  751.                    bufp->fastmap))
  752.         return;
  753.     if (PyErr_Occurred()) return;
  754.     if (bufp->buffer[0] == Cbol)
  755.         bufp->anchor = 1;   /* begline */
  756.     else
  757.         if (bufp->buffer[0] == Cbegbuf)
  758.             bufp->anchor = 2; /* begbuf */
  759.         else
  760.             bufp->anchor = 0; /* none */
  761.     bufp->fastmap_accurate = 1;
  762. }
  763.  
  764. /* 
  765.  * star is coded as:
  766.  * 1: failure_jump 2
  767.  *    ... code for operand of star
  768.  *    star_jump 1
  769.  * 2: ... code after star
  770.  *
  771.  * We change the star_jump to update_failure_jump if we can determine
  772.  * that it is safe to do so; otherwise we change it to an ordinary
  773.  * jump.
  774.  *
  775.  * plus is coded as
  776.  *
  777.  *    jump 2
  778.  * 1: failure_jump 3
  779.  * 2: ... code for operand of plus
  780.  *    star_jump 1
  781.  * 3: ... code after plus
  782.  *
  783.  * For star_jump considerations this is processed identically to star.
  784.  *
  785.  */
  786.  
  787. static int re_optimize_star_jump(bufp, code)
  788.     regexp_t bufp;
  789.     unsigned char *code;
  790. {
  791.     unsigned char map[256];
  792.     unsigned char can_be_null;
  793.     unsigned char *p1;
  794.     unsigned char *p2;
  795.     unsigned char ch;
  796.     int a;
  797.     int b;
  798.     int num_instructions = 0;
  799.  
  800.     a = (unsigned char)*code++;
  801.     a |= (unsigned char)*code++ << 8;
  802.     a = (int)SHORT(a);
  803.     
  804.     p1 = code + a + 3; /* skip the failure_jump */
  805.     /* Check that the jump is within the pattern */
  806.     if (p1<bufp->buffer || bufp->buffer+bufp->used<p1)
  807.       {
  808.         PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (failure_jump opt)");
  809.         return 0;
  810.       }
  811.     
  812.     assert(p1[-3] == Cfailure_jump);
  813.     p2 = code;
  814.     /* p1 points inside loop, p2 points to after loop */
  815.     if (!re_do_compile_fastmap(bufp->buffer, bufp->used,
  816.                    p2 - bufp->buffer, &can_be_null, map))
  817.         goto make_normal_jump;
  818.     
  819.     /* If we might introduce a new update point inside the
  820.      * loop, we can't optimize because then update_jump would
  821.      * update a wrong failure point.  Thus we have to be
  822.      * quite careful here.
  823.      */
  824.     
  825.     /* loop until we find something that consumes a character */
  826.   loop_p1:
  827.     num_instructions++;
  828.     switch (*p1++)
  829.     {
  830.     case Cbol:
  831.     case Ceol:
  832.     case Cbegbuf:
  833.     case Cendbuf:
  834.     case Cwordbeg:
  835.     case Cwordend:
  836.     case Cwordbound:
  837.     case Cnotwordbound:
  838.     {
  839.         goto loop_p1;
  840.     }
  841.     case Cstart_memory:
  842.     case Cend_memory:
  843.     {
  844.         p1++;
  845.         goto loop_p1;
  846.     }
  847.     case Cexact:
  848.     {
  849.         ch = (unsigned char)*p1++;
  850.         if (map[(int)ch])
  851.             goto make_normal_jump;
  852.         break;
  853.     }
  854.     case Canychar:
  855.     {
  856.         for (b = 0; b < 256; b++)
  857.             if (b != '\n' && map[b])
  858.                 goto make_normal_jump;
  859.         break;
  860.     }
  861.     case Cset:
  862.     {
  863.         for (b = 0; b < 256; b++)
  864.             if ((p1[b >> 3] & (1 << (b & 7))) && map[b])
  865.                 goto make_normal_jump;
  866.         p1 += 256/8;
  867.         break;
  868.     }
  869.     default:
  870.     {
  871.         goto make_normal_jump;
  872.     }
  873.     }
  874.     /* now we know that we can't backtrack. */
  875.     while (p1 != p2 - 3)
  876.     {
  877.         num_instructions++;
  878.         switch (*p1++)
  879.         {
  880.         case Cend:
  881.         {
  882.             return 0;
  883.         }
  884.         case Cbol:
  885.         case Ceol:
  886.         case Canychar:
  887.         case Cbegbuf:
  888.         case Cendbuf:
  889.         case Cwordbeg:
  890.         case Cwordend:
  891.         case Cwordbound:
  892.         case Cnotwordbound:
  893.         {
  894.             break;
  895.         }
  896.         case Cset:
  897.         {
  898.             p1 += 256/8;
  899.             break;
  900.         }
  901.         case Cexact:
  902.         case Cstart_memory:
  903.         case Cend_memory:
  904.         case Cmatch_memory:
  905.         case Csyntaxspec:
  906.         case Cnotsyntaxspec:
  907.         {
  908.             p1++;
  909.             break;
  910.         }
  911.         case Cjump:
  912.         case Cstar_jump:
  913.         case Cfailure_jump:
  914.         case Cupdate_failure_jump:
  915.         case Cdummy_failure_jump:
  916.         {
  917.             goto make_normal_jump;
  918.         }
  919.         default:
  920.         {
  921.             return 0;
  922.             break;
  923.         }
  924.         }
  925.     }
  926.     
  927.     /* make_update_jump: */
  928.     code -= 3;
  929.     a += 3;  /* jump to after the Cfailure_jump */
  930.     code[0] = Cupdate_failure_jump;
  931.     code[1] = a & 0xff;
  932.     code[2] = a >> 8;
  933.     if (num_instructions > 1)
  934.         return 1;
  935.     assert(num_instructions == 1);
  936.     /* if the only instruction matches a single character, we can do
  937.      * better */
  938.     p1 = code + 3 + a;   /* start of sole instruction */
  939.     if (*p1 == Cset || *p1 == Cexact || *p1 == Canychar ||
  940.         *p1 == Csyntaxspec || *p1 == Cnotsyntaxspec)
  941.         code[0] = Crepeat1;
  942.     return 1;
  943.     
  944.   make_normal_jump:
  945.     code -= 3;
  946.     *code = Cjump;
  947.     return 1;
  948. }
  949.  
  950. static int re_optimize(bufp)
  951.     regexp_t bufp;
  952. {
  953.     unsigned char *code;
  954.     
  955.     code = bufp->buffer;
  956.     
  957.     while(1)
  958.     {
  959.         switch (*code++)
  960.         {
  961.         case Cend:
  962.         {
  963.             return 1;
  964.         }
  965.         case Canychar:
  966.         case Cbol:
  967.         case Ceol:
  968.         case Cbegbuf:
  969.         case Cendbuf:
  970.         case Cwordbeg:
  971.         case Cwordend:
  972.         case Cwordbound:
  973.         case Cnotwordbound:
  974.         {
  975.             break;
  976.         }
  977.         case Cset:
  978.         {
  979.             code += 256/8;
  980.             break;
  981.         }
  982.         case Cexact:
  983.         case Cstart_memory:
  984.         case Cend_memory:
  985.         case Cmatch_memory:
  986.         case Csyntaxspec:
  987.         case Cnotsyntaxspec:
  988.         {
  989.             code++;
  990.             break;
  991.         }
  992.         case Cstar_jump:
  993.         {
  994.             if (!re_optimize_star_jump(bufp, code))
  995.             {
  996.                 return 0;
  997.             }
  998.             /* fall through */
  999.         }
  1000.         case Cupdate_failure_jump:
  1001.         case Cjump:
  1002.         case Cdummy_failure_jump:
  1003.         case Cfailure_jump:
  1004.         case Crepeat1:
  1005.         {
  1006.             code += 2;
  1007.             break;
  1008.         }
  1009.         default:
  1010.         {
  1011.             return 0;
  1012.         }
  1013.         }
  1014.     }
  1015. }
  1016.  
  1017. #define NEXTCHAR(var) \
  1018. { \
  1019.     if (pos >= size) \
  1020.         goto ends_prematurely; \
  1021.     (var) = regex[pos]; \
  1022.     pos++; \
  1023. }
  1024.  
  1025. #define ALLOC(amount) \
  1026. { \
  1027.       if (pattern_offset+(amount) > alloc) \
  1028.       { \
  1029.           alloc += 256 + (amount); \
  1030.           pattern = realloc(pattern, alloc); \
  1031.           if (!pattern) \
  1032.               goto out_of_memory; \
  1033.       } \
  1034. }
  1035.  
  1036. #define STORE(ch) pattern[pattern_offset++] = (ch)
  1037.  
  1038. #define CURRENT_LEVEL_START (starts[starts_base + current_level])
  1039.  
  1040. #define SET_LEVEL_START starts[starts_base + current_level] = pattern_offset
  1041.  
  1042. #define PUSH_LEVEL_STARTS \
  1043. if (starts_base < (MAX_NESTING-1)*NUM_LEVELS) \
  1044.     starts_base += NUM_LEVELS; \
  1045. else \
  1046.     goto too_complex \
  1047.  
  1048. #define POP_LEVEL_STARTS starts_base -= NUM_LEVELS
  1049.  
  1050. #define PUT_ADDR(offset,addr) \
  1051. { \
  1052.     int disp = (addr) - (offset) - 2; \
  1053.     pattern[(offset)] = disp & 0xff; \
  1054.     pattern[(offset)+1] = (disp>>8) & 0xff; \
  1055. }
  1056.  
  1057. #define INSERT_JUMP(pos,type,addr) \
  1058. { \
  1059.     int a, p = (pos), t = (type), ad = (addr); \
  1060.     for (a = pattern_offset - 1; a >= p; a--) \
  1061.         pattern[a + 3] = pattern[a]; \
  1062.     pattern[p] = t; \
  1063.     PUT_ADDR(p+1,ad); \
  1064.     pattern_offset += 3; \
  1065. }
  1066.  
  1067. #define SETBIT(buf,offset,bit) (buf)[(offset)+(bit)/8] |= (1<<((bit) & 7))
  1068.  
  1069. #define SET_FIELDS \
  1070. { \
  1071.     bufp->allocated = alloc; \
  1072.     bufp->buffer = pattern; \
  1073.     bufp->used = pattern_offset; \
  1074. }
  1075.     
  1076. #define GETHEX(var) \
  1077. { \
  1078.     unsigned char gethex_ch, gethex_value; \
  1079.     NEXTCHAR(gethex_ch); \
  1080.     gethex_value = hex_char_to_decimal(gethex_ch); \
  1081.     if (gethex_value == 16) \
  1082.         goto hex_error; \
  1083.     NEXTCHAR(gethex_ch); \
  1084.     gethex_ch = hex_char_to_decimal(gethex_ch); \
  1085.     if (gethex_ch == 16) \
  1086.         goto hex_error; \
  1087.     (var) = gethex_value * 16 + gethex_ch; \
  1088. }
  1089.  
  1090. #define ANSI_TRANSLATE(ch) \
  1091. { \
  1092.     switch (ch) \
  1093.     { \
  1094.     case 'a': \
  1095.     case 'A': \
  1096.     { \
  1097.         ch = 7; /* audible bell */ \
  1098.         break; \
  1099.     } \
  1100.     case 'b': \
  1101.     case 'B': \
  1102.     { \
  1103.         ch = 8; /* backspace */ \
  1104.         break; \
  1105.     } \
  1106.     case 'f': \
  1107.     case 'F': \
  1108.     { \
  1109.         ch = 12; /* form feed */ \
  1110.         break; \
  1111.     } \
  1112.     case 'n': \
  1113.     case 'N': \
  1114.     { \
  1115.         ch = 10; /* line feed */ \
  1116.         break; \
  1117.     } \
  1118.     case 'r': \
  1119.     case 'R': \
  1120.     { \
  1121.         ch = 13; /* carriage return */ \
  1122.         break; \
  1123.     } \
  1124.     case 't': \
  1125.     case 'T': \
  1126.     { \
  1127.           ch = 9; /* tab */ \
  1128.           break; \
  1129.     } \
  1130.     case 'v': \
  1131.     case 'V': \
  1132.     { \
  1133.         ch = 11; /* vertical tab */ \
  1134.         break; \
  1135.     } \
  1136.     case 'x': /* hex code */ \
  1137.     case 'X': \
  1138.     { \
  1139.         GETHEX(ch); \
  1140.         break; \
  1141.     } \
  1142.     default: \
  1143.     { \
  1144.         /* other characters passed through */ \
  1145.         if (translate) \
  1146.             ch = translate[(unsigned char)ch]; \
  1147.         break; \
  1148.     } \
  1149.     } \
  1150. }
  1151.  
  1152. char *re_compile_pattern(regex, size, bufp)
  1153.     unsigned char *regex;
  1154.     int size;
  1155.     regexp_t bufp;
  1156. {
  1157.     int a;
  1158.     int pos;
  1159.     int op;
  1160.     int current_level;
  1161.     int level;
  1162.     int opcode;
  1163.     int pattern_offset = 0, alloc;
  1164.     int starts[NUM_LEVELS * MAX_NESTING];
  1165.     int starts_base;
  1166.     int future_jumps[MAX_NESTING];
  1167.     int num_jumps;
  1168.     unsigned char ch = '\0';
  1169.     unsigned char *pattern;
  1170.     unsigned char *translate;
  1171.     int next_register;
  1172.     int paren_depth;
  1173.     int num_open_registers;
  1174.     int open_registers[RE_NREGS];
  1175.     int beginning_context;
  1176.     
  1177.     if (!re_compile_initialized)
  1178.         re_compile_initialize();
  1179.     bufp->used = 0;
  1180.     bufp->fastmap_accurate = 0;
  1181.     bufp->uses_registers = 1;
  1182.     bufp->num_registers = 1;
  1183.     translate = bufp->translate;
  1184.     pattern = bufp->buffer;
  1185.     alloc = bufp->allocated;
  1186.     if (alloc == 0 || pattern == NULL)
  1187.     {
  1188.         alloc = 256;
  1189.         pattern = malloc(alloc);
  1190.         if (!pattern)
  1191.             goto out_of_memory;
  1192.     }
  1193.     pattern_offset = 0;
  1194.     starts_base = 0;
  1195.     num_jumps = 0;
  1196.     current_level = 0;
  1197.     SET_LEVEL_START;
  1198.     num_open_registers = 0;
  1199.     next_register = 1;
  1200.     paren_depth = 0;
  1201.     beginning_context = 1;
  1202.     op = -1;
  1203.     /* we use Rend dummy to ensure that pending jumps are updated
  1204.        (due to low priority of Rend) before exiting the loop. */
  1205.     pos = 0;
  1206.     while (op != Rend)
  1207.     {
  1208.         if (pos >= size)
  1209.             op = Rend;
  1210.         else
  1211.         {
  1212.             NEXTCHAR(ch);
  1213.             if (translate)
  1214.                 ch = translate[(unsigned char)ch];
  1215.             op = regexp_plain_ops[(unsigned char)ch];
  1216.             if (op == Rquote)
  1217.             {
  1218.                 NEXTCHAR(ch);
  1219.                 op = regexp_quoted_ops[(unsigned char)ch];
  1220.                 if (op == Rnormal && regexp_ansi_sequences)
  1221.                     ANSI_TRANSLATE(ch);
  1222.             }
  1223.         }
  1224.         level = regexp_precedences[op];
  1225.         /* printf("ch='%c' op=%d level=%d current_level=%d
  1226.            curlevstart=%d\n", ch, op, level, current_level,
  1227.            CURRENT_LEVEL_START); */
  1228.         if (level > current_level)
  1229.         {
  1230.             for (current_level++; current_level < level; current_level++)
  1231.                 SET_LEVEL_START;
  1232.             SET_LEVEL_START;
  1233.         }
  1234.         else
  1235.             if (level < current_level)
  1236.             {
  1237.                 current_level = level;
  1238.                 for (;num_jumps > 0 &&
  1239.                          future_jumps[num_jumps-1] >= CURRENT_LEVEL_START;
  1240.                      num_jumps--)
  1241.                     PUT_ADDR(future_jumps[num_jumps-1], pattern_offset);
  1242.             }
  1243.         switch (op)
  1244.         {
  1245.         case Rend:
  1246.         {
  1247.             break;
  1248.         }
  1249.         case Rnormal:
  1250.         {
  1251.           normal_char:
  1252.             opcode = Cexact;
  1253.           store_opcode_and_arg: /* opcode & ch must be set */
  1254.             SET_LEVEL_START;
  1255.             ALLOC(2);
  1256.             STORE(opcode);
  1257.             STORE(ch);
  1258.             break;
  1259.         }
  1260.         case Ranychar:
  1261.         {
  1262.             opcode = Canychar;
  1263.           store_opcode:
  1264.             SET_LEVEL_START;
  1265.             ALLOC(1);
  1266.             STORE(opcode);
  1267.             break;
  1268.         }
  1269.         case Rquote:
  1270.         {
  1271.             abort();
  1272.             /*NOTREACHED*/
  1273.         }
  1274.         case Rbol:
  1275.         {
  1276.             if (!beginning_context) {
  1277.                 if (regexp_context_indep_ops)
  1278.                     goto op_error;
  1279.                 else
  1280.                     goto normal_char;
  1281.             }
  1282.             opcode = Cbol;
  1283.             goto store_opcode;
  1284.         }
  1285.         case Reol:
  1286.         {
  1287.             if (!((pos >= size) ||
  1288.                   ((regexp_syntax & RE_NO_BK_VBAR) ?
  1289.                    (regex[pos] == '\174') :
  1290.                    (pos+1 < size && regex[pos] == '\134' &&
  1291.                 regex[pos+1] == '\174')) ||
  1292.                   ((regexp_syntax & RE_NO_BK_PARENS)?
  1293.                    (regex[pos] == ')'):
  1294.                    (pos+1 < size && regex[pos] == '\134' &&
  1295.                 regex[pos+1] == ')')))) {
  1296.                 if (regexp_context_indep_ops)
  1297.                     goto op_error;
  1298.                 else
  1299.                     goto normal_char;
  1300.             }
  1301.             opcode = Ceol;
  1302.             goto store_opcode;
  1303.             /* NOTREACHED */
  1304.             break;
  1305.         }
  1306.         case Roptional:
  1307.         {
  1308.             if (beginning_context) {
  1309.                 if (regexp_context_indep_ops)
  1310.                     goto op_error;
  1311.                 else
  1312.                     goto normal_char;
  1313.             }
  1314.             if (CURRENT_LEVEL_START == pattern_offset)
  1315.                 break; /* ignore empty patterns for ? */
  1316.             ALLOC(3);
  1317.             INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
  1318.                     pattern_offset + 3);
  1319.             break;
  1320.         }
  1321.         case Rstar:
  1322.         case Rplus:
  1323.         {
  1324.             if (beginning_context) {
  1325.                 if (regexp_context_indep_ops)
  1326.                     goto op_error;
  1327.                 else
  1328.                     goto normal_char;
  1329.             }
  1330.             if (CURRENT_LEVEL_START == pattern_offset)
  1331.                 break; /* ignore empty patterns for + and * */
  1332.             ALLOC(9);
  1333.             INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
  1334.                     pattern_offset + 6);
  1335.             INSERT_JUMP(pattern_offset, Cstar_jump, CURRENT_LEVEL_START);
  1336.             if (op == Rplus)  /* jump over initial failure_jump */
  1337.                 INSERT_JUMP(CURRENT_LEVEL_START, Cdummy_failure_jump,
  1338.                         CURRENT_LEVEL_START + 6);
  1339.             break;
  1340.         }
  1341.         case Ror:
  1342.         {
  1343.             ALLOC(6);
  1344.             INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
  1345.                     pattern_offset + 6);
  1346.             if (num_jumps >= MAX_NESTING)
  1347.                 goto too_complex;
  1348.             STORE(Cjump);
  1349.             future_jumps[num_jumps++] = pattern_offset;
  1350.             STORE(0);
  1351.             STORE(0);
  1352.             SET_LEVEL_START;
  1353.             break;
  1354.         }
  1355.         case Ropenpar:
  1356.         {
  1357.             SET_LEVEL_START;
  1358.             if (next_register < RE_NREGS)
  1359.             {
  1360.                 bufp->uses_registers = 1;
  1361.                 ALLOC(2);
  1362.                 STORE(Cstart_memory);
  1363.                 STORE(next_register);
  1364.                 open_registers[num_open_registers++] = next_register;
  1365.                 bufp->num_registers++;
  1366.                 next_register++;
  1367.             }
  1368.             paren_depth++;
  1369.             PUSH_LEVEL_STARTS;
  1370.             current_level = 0;
  1371.             SET_LEVEL_START;
  1372.             break;
  1373.         }
  1374.         case Rclosepar:
  1375.         {
  1376.             if (paren_depth <= 0)
  1377.                 goto parenthesis_error;
  1378.             POP_LEVEL_STARTS;
  1379.             current_level = regexp_precedences[Ropenpar];
  1380.             paren_depth--;
  1381.             if (paren_depth < num_open_registers)
  1382.             {
  1383.                 bufp->uses_registers = 1;
  1384.                 ALLOC(2);
  1385.                 STORE(Cend_memory);
  1386.                 num_open_registers--;
  1387.                 STORE(open_registers[num_open_registers]);
  1388.             }
  1389.             break;
  1390.         }
  1391.         case Rmemory:
  1392.         {
  1393.             if (ch == '0')
  1394.                 goto bad_match_register;
  1395.             assert(ch >= '0' && ch <= '9');
  1396.             bufp->uses_registers = 1;
  1397.             opcode = Cmatch_memory;
  1398.             ch -= '0';
  1399.             goto store_opcode_and_arg;
  1400.         }
  1401.         case Rextended_memory:
  1402.         {
  1403.             NEXTCHAR(ch);
  1404.             if (ch < '0' || ch > '9')
  1405.                 goto bad_match_register;
  1406.             NEXTCHAR(a);
  1407.             if (a < '0' || a > '9')
  1408.                 goto bad_match_register;
  1409.             ch = 10 * (a - '0') + ch - '0';
  1410.             if (ch <= 0 || ch >= RE_NREGS)
  1411.                 goto bad_match_register;
  1412.             bufp->uses_registers = 1;
  1413.             opcode = Cmatch_memory;
  1414.             goto store_opcode_and_arg;
  1415.         }
  1416.         case Ropenset:
  1417.         {
  1418.             int complement;
  1419.             int prev;
  1420.             int offset;
  1421.             int range;
  1422.             int firstchar;
  1423.         
  1424.             SET_LEVEL_START;
  1425.             ALLOC(1+256/8);
  1426.             STORE(Cset);
  1427.             offset = pattern_offset;
  1428.             for (a = 0; a < 256/8; a++)
  1429.                 STORE(0);
  1430.             NEXTCHAR(ch);
  1431.             if (translate)
  1432.                 ch = translate[(unsigned char)ch];
  1433.             if (ch == '\136')
  1434.             {
  1435.                 complement = 1;
  1436.                 NEXTCHAR(ch);
  1437.                 if (translate)
  1438.                     ch = translate[(unsigned char)ch];
  1439.             }
  1440.             else
  1441.                 complement = 0;
  1442.             prev = -1;
  1443.             range = 0;
  1444.             firstchar = 1;
  1445.             while (ch != '\135' || firstchar)
  1446.             {
  1447.                 firstchar = 0;
  1448.                 if (regexp_ansi_sequences && ch == '\134')
  1449.                 {
  1450.                     NEXTCHAR(ch);
  1451.                     ANSI_TRANSLATE(ch);
  1452.                 }
  1453.                 if (range)
  1454.                 {
  1455.                     for (a = prev; a <= (int)ch; a++)
  1456.                         SETBIT(pattern, offset, a);
  1457.                     prev = -1;
  1458.                     range = 0;
  1459.                 }
  1460.                 else
  1461.                     if (prev != -1 && ch == '-')
  1462.                         range = 1;
  1463.                     else
  1464.                     {
  1465.                         SETBIT(pattern, offset, ch);
  1466.                         prev = ch;
  1467.                     }
  1468.                 NEXTCHAR(ch);
  1469.                 if (translate)
  1470.                     ch = translate[(unsigned char)ch];
  1471.             }
  1472.             if (range)
  1473.                 SETBIT(pattern, offset, '-');
  1474.             if (complement)
  1475.             {
  1476.                 for (a = 0; a < 256/8; a++)
  1477.                     pattern[offset+a] ^= 0xff;
  1478.             }
  1479.             break;
  1480.         }
  1481.         case Rbegbuf:
  1482.         {
  1483.             opcode = Cbegbuf;
  1484.             goto store_opcode;
  1485.         }
  1486.         case Rendbuf:
  1487.         {
  1488.             opcode = Cendbuf;
  1489.             goto store_opcode;
  1490.         }
  1491.         case Rwordchar:
  1492.         {
  1493.             opcode = Csyntaxspec;
  1494.             ch = Sword;
  1495.             goto store_opcode_and_arg;
  1496.         }
  1497.         case Rnotwordchar:
  1498.         {
  1499.             opcode = Cnotsyntaxspec;
  1500.             ch = Sword;
  1501.             goto store_opcode_and_arg;
  1502.         }
  1503.         case Rwordbeg:
  1504.         {
  1505.             opcode = Cwordbeg;
  1506.             goto store_opcode;
  1507.         }
  1508.         case Rwordend:
  1509.         {
  1510.             opcode = Cwordend;
  1511.             goto store_opcode;
  1512.         }
  1513.         case Rwordbound:
  1514.         {
  1515.             opcode = Cwordbound;
  1516.             goto store_opcode;
  1517.         }
  1518.         case Rnotwordbound:
  1519.         {
  1520.             opcode = Cnotwordbound;
  1521.             goto store_opcode;
  1522.         }
  1523.         default:
  1524.         {
  1525.             abort();
  1526.         }
  1527.         }
  1528.         beginning_context = (op == Ropenpar || op == Ror);
  1529.     }
  1530.     if (starts_base != 0)
  1531.         goto parenthesis_error;
  1532.     assert(num_jumps == 0);
  1533.     ALLOC(1);
  1534.     STORE(Cend);
  1535.     SET_FIELDS;
  1536.     if(!re_optimize(bufp))
  1537.         return "Optimization error";
  1538.     return NULL;
  1539.  
  1540.   op_error:
  1541.     SET_FIELDS;
  1542.     return "Badly placed special character";
  1543.  
  1544.   bad_match_register:
  1545.     SET_FIELDS;
  1546.     return "Bad match register number";
  1547.    
  1548.   hex_error:
  1549.     SET_FIELDS;
  1550.     return "Bad hexadecimal number";
  1551.    
  1552.   parenthesis_error:
  1553.     SET_FIELDS;
  1554.     return "Badly placed parenthesis";
  1555.    
  1556.   out_of_memory:
  1557.     SET_FIELDS;
  1558.     return "Out of memory";
  1559.    
  1560.   ends_prematurely:
  1561.     SET_FIELDS;
  1562.     return "Regular expression ends prematurely";
  1563.  
  1564.   too_complex:
  1565.     SET_FIELDS;
  1566.     return "Regular expression too complex";
  1567. }
  1568.  
  1569. #undef CHARAT
  1570. #undef NEXTCHAR
  1571. #undef GETHEX
  1572. #undef ALLOC
  1573. #undef STORE
  1574. #undef CURRENT_LEVEL_START
  1575. #undef SET_LEVEL_START
  1576. #undef PUSH_LEVEL_STARTS
  1577. #undef POP_LEVEL_STARTS
  1578. #undef PUT_ADDR
  1579. #undef INSERT_JUMP
  1580. #undef SETBIT
  1581. #undef SET_FIELDS
  1582.  
  1583. #define PREFETCH if (text == textend) goto fail
  1584.  
  1585. #define NEXTCHAR(var) \
  1586. PREFETCH; \
  1587. var = (unsigned char)*text++; \
  1588. if (translate) \
  1589.     var = translate[var]
  1590.  
  1591. int re_match(bufp,
  1592.          string,
  1593.          size,
  1594.          pos,
  1595.          old_regs)
  1596.     regexp_t bufp;
  1597.     unsigned char *string;
  1598.     int size;
  1599.     int pos;
  1600.     regexp_registers_t old_regs;
  1601. {
  1602.     unsigned char *code;
  1603.     unsigned char *translate;
  1604.     unsigned char *text;
  1605.     unsigned char *textstart;
  1606.     unsigned char *textend;
  1607.     int a;
  1608.     int b;
  1609.     int ch;
  1610.     int reg;
  1611.     int match_end;
  1612.     unsigned char *regstart;
  1613.     unsigned char *regend;
  1614.     int regsize;
  1615.     match_state state;
  1616.   
  1617.     assert(pos >= 0 && size >= 0);
  1618.     assert(pos <= size);
  1619.   
  1620.     text = string + pos;
  1621.     textstart = string;
  1622.     textend = string + size;
  1623.   
  1624.     code = bufp->buffer;
  1625.   
  1626.     translate = bufp->translate;
  1627.   
  1628.     NEW_STATE(state, bufp->num_registers);
  1629.  
  1630.   continue_matching:
  1631.     switch (*code++)
  1632.     {
  1633.     case Cend:
  1634.     {
  1635.         match_end = text - textstart;
  1636.         if (old_regs)
  1637.         {
  1638.             old_regs->start[0] = pos;
  1639.             old_regs->end[0] = match_end;
  1640.             if (!bufp->uses_registers)
  1641.             {
  1642.                 for (a = 1; a < RE_NREGS; a++)
  1643.                 {
  1644.                     old_regs->start[a] = -1;
  1645.                     old_regs->end[a] = -1;
  1646.                 }
  1647.             }
  1648.             else
  1649.             {
  1650.                 for (a = 1; a < bufp->num_registers; a++)
  1651.                 {
  1652.                     if ((GET_REG_START(state, a) == NULL) ||
  1653.                         (GET_REG_END(state, a) == NULL))
  1654.                     {
  1655.                         old_regs->start[a] = -1;
  1656.                         old_regs->end[a] = -1;
  1657.                         continue;
  1658.                     }
  1659.                     old_regs->start[a] = GET_REG_START(state, a) - textstart;
  1660.                     old_regs->end[a] = GET_REG_END(state, a) - textstart;
  1661.                 }
  1662.                 for (; a < RE_NREGS; a++)
  1663.                 {
  1664.                     old_regs->start[a] = -1;
  1665.                     old_regs->end[a] = -1;
  1666.                 }
  1667.             }
  1668.         }
  1669.         FREE_STATE(state);
  1670.         return match_end - pos;
  1671.     }
  1672.     case Cbol:
  1673.     {
  1674.         if (text == textstart || text[-1] == '\n')
  1675.             goto continue_matching;
  1676.         goto fail;
  1677.     }
  1678.     case Ceol:
  1679.     {
  1680.         if (text == textend || *text == '\n')
  1681.             goto continue_matching;
  1682.         goto fail;
  1683.     }
  1684.     case Cset:
  1685.     {
  1686.         NEXTCHAR(ch);
  1687.         if (code[ch/8] & (1<<(ch & 7)))
  1688.         {
  1689.             code += 256/8;
  1690.             goto continue_matching;
  1691.         }
  1692.         goto fail;
  1693.     }
  1694.     case Cexact:
  1695.     {
  1696.         NEXTCHAR(ch);
  1697.         if (ch != (unsigned char)*code++)
  1698.             goto fail;
  1699.         goto continue_matching;
  1700.     }
  1701.     case Canychar:
  1702.     {
  1703.         NEXTCHAR(ch);
  1704.         if (ch == '\n')
  1705.             goto fail;
  1706.         goto continue_matching;
  1707.     }
  1708.     case Cstart_memory:
  1709.     {
  1710.         reg = *code++;
  1711.         SET_REG_START(state, reg, text, goto error);
  1712.         goto continue_matching;
  1713.     }
  1714.     case Cend_memory:
  1715.     {
  1716.         reg = *code++;
  1717.         SET_REG_END(state, reg, text, goto error);
  1718.         goto continue_matching;
  1719.     }
  1720.     case Cmatch_memory:
  1721.     {
  1722.         reg = *code++;
  1723.         regstart = GET_REG_START(state, reg);
  1724.         regend = GET_REG_END(state, reg);
  1725.         if ((regstart == NULL) || (regend == NULL))
  1726.             goto fail;  /* or should we just match nothing? */
  1727.         regsize = regend - regstart;
  1728.  
  1729.         if (regsize > (textend - text))
  1730.             goto fail;
  1731.         if(translate)
  1732.         {
  1733.             for (; regstart < regend; regstart++, text++)
  1734.                 if (translate[*regstart] != translate[*text])
  1735.                     goto fail;
  1736.         }
  1737.         else
  1738.             for (; regstart < regend; regstart++, text++)
  1739.                 if (*regstart != *text)
  1740.                     goto fail;
  1741.         goto continue_matching;
  1742.     }
  1743.     case Cupdate_failure_jump:
  1744.     {
  1745.         UPDATE_FAILURE(state, text, goto error);
  1746.         /* fall to next case */
  1747.     }
  1748.     /* treat Cstar_jump just like Cjump if it hasn't been optimized */
  1749.     case Cstar_jump:
  1750.     case Cjump:
  1751.     {
  1752.         a = (unsigned char)*code++;
  1753.         a |= (unsigned char)*code++ << 8;
  1754.         code += (int)SHORT(a);
  1755.         if (code<bufp->buffer || bufp->buffer+bufp->used<code) {
  1756.                 PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cjump)");
  1757.             FREE_STATE(state);
  1758.                         return -2;
  1759.              }
  1760.         goto continue_matching;
  1761.     }
  1762.     case Cdummy_failure_jump:
  1763.     {
  1764.                 unsigned char *failuredest;
  1765.       
  1766.         a = (unsigned char)*code++;
  1767.         a |= (unsigned char)*code++ << 8;
  1768.         a = (int)SHORT(a);
  1769.         assert(*code == Cfailure_jump);
  1770.         b = (unsigned char)code[1];
  1771.         b |= (unsigned char)code[2] << 8;
  1772.                 failuredest = code + (int)SHORT(b) + 3;
  1773.         if (failuredest<bufp->buffer || bufp->buffer+bufp->used < failuredest) {
  1774.                 PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cdummy_failure_jump failuredest)");
  1775.             FREE_STATE(state);
  1776.                         return -2;
  1777.         }
  1778.         PUSH_FAILURE(state, failuredest, NULL, goto error);
  1779.         code += a;
  1780.         if (code<bufp->buffer || bufp->buffer+bufp->used < code) {
  1781.                 PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cdummy_failure_jump code)");
  1782.             FREE_STATE(state);
  1783.                         return -2;
  1784.              }
  1785.         goto continue_matching;
  1786.     }
  1787.     case Cfailure_jump:
  1788.     {
  1789.         a = (unsigned char)*code++;
  1790.         a |= (unsigned char)*code++ << 8;
  1791.         a = (int)SHORT(a);
  1792.         if (code+a<bufp->buffer || bufp->buffer+bufp->used < code+a) {
  1793.                 PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cfailure_jump)");
  1794.             FREE_STATE(state);
  1795.                         return -2;
  1796.              }
  1797.         PUSH_FAILURE(state, code + a, text, goto error);
  1798.         goto continue_matching;
  1799.     }
  1800.     case Crepeat1:
  1801.     {
  1802.         unsigned char *pinst;
  1803.         a = (unsigned char)*code++;
  1804.         a |= (unsigned char)*code++ << 8;
  1805.         a = (int)SHORT(a);
  1806.         pinst = code + a;
  1807.         if (pinst<bufp->buffer || bufp->buffer+bufp->used<pinst) {
  1808.                 PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Crepeat1)");
  1809.             FREE_STATE(state);
  1810.                         return -2;
  1811.              }
  1812.         /* pinst is sole instruction in loop, and it matches a
  1813.          * single character.  Since Crepeat1 was originally a
  1814.          * Cupdate_failure_jump, we also know that backtracking
  1815.          * is useless: so long as the single-character
  1816.          * expression matches, it must be used.  Also, in the
  1817.          * case of +, we've already matched one character, so +
  1818.          * can't fail: nothing here can cause a failure.  */
  1819.         switch (*pinst++)
  1820.         {
  1821.         case Cset:
  1822.           {
  1823.                 if (translate)
  1824.             {
  1825.                 while (text < textend)
  1826.                 {
  1827.                     ch = translate[(unsigned char)*text];
  1828.                     if (pinst[ch/8] & (1<<(ch & 7)))
  1829.                         text++;
  1830.                     else
  1831.                         break;
  1832.                 }
  1833.             }
  1834.             else
  1835.             {
  1836.                 while (text < textend)
  1837.                 {
  1838.                     ch = (unsigned char)*text;
  1839.                     if (pinst[ch/8] & (1<<(ch & 7)))
  1840.                         text++;
  1841.                     else
  1842.                         break;
  1843.                 }
  1844.             }
  1845.             break;
  1846.                 }
  1847.         case Cexact:
  1848.         {
  1849.             ch = (unsigned char)*pinst;
  1850.             if (translate)
  1851.             {
  1852.                 while (text < textend &&
  1853.                        translate[(unsigned char)*text] == ch)
  1854.                     text++;
  1855.             }
  1856.             else
  1857.             {
  1858.                 while (text < textend && (unsigned char)*text == ch)
  1859.                     text++;
  1860.             }
  1861.             break;
  1862.         }
  1863.         case Canychar:
  1864.         {
  1865.             while (text < textend && (unsigned char)*text != '\n')
  1866.                 text++;
  1867.             break;
  1868.         }
  1869.         case Csyntaxspec:
  1870.         {
  1871.             a = (unsigned char)*pinst;
  1872.             if (translate)
  1873.             {
  1874.                 while (text < textend &&
  1875.                        (SYNTAX(translate[*text]) & a) )
  1876.                     text++;
  1877.             }
  1878.             else
  1879.             {
  1880.                 while (text < textend && (SYNTAX(*text) & a) )
  1881.                     text++;
  1882.             }
  1883.             break;
  1884.         }
  1885.         case Cnotsyntaxspec:
  1886.         {
  1887.             a = (unsigned char)*pinst;
  1888.             if (translate)
  1889.             {
  1890.                 while (text < textend &&
  1891.                        !(SYNTAX(translate[*text]) & a) )
  1892.                     text++;
  1893.             }
  1894.             else
  1895.             {
  1896.                 while (text < textend && !(SYNTAX(*text) & a) )
  1897.                     text++;
  1898.             }
  1899.             break;
  1900.         }
  1901.         default:
  1902.         {
  1903.                 FREE_STATE(state);
  1904.                 PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");
  1905.                 return -2;
  1906.             /*NOTREACHED*/
  1907.         }
  1908.         }
  1909.         /* due to the funky way + and * are compiled, the top
  1910.          * failure- stack entry at this point is actually a
  1911.          * success entry -- update it & pop it */
  1912.         UPDATE_FAILURE(state, text, goto error);
  1913.         goto fail;      /* i.e., succeed <wink/sigh> */
  1914.     }
  1915.     case Cbegbuf:
  1916.     {
  1917.         if (text == textstart)
  1918.             goto continue_matching;
  1919.         goto fail;
  1920.     }
  1921.     case Cendbuf:
  1922.     {
  1923.         if (text == textend)
  1924.             goto continue_matching;
  1925.         goto fail;
  1926.     }
  1927.     case Cwordbeg:
  1928.     {
  1929.         if (text == textend)
  1930.             goto fail;
  1931.         if (!(SYNTAX(*text) & Sword)) 
  1932.             goto fail;
  1933.         if (text == textstart)
  1934.             goto continue_matching;
  1935.         if (!(SYNTAX(text[-1]) & Sword))
  1936.             goto continue_matching;
  1937.         goto fail;
  1938.     }
  1939.     case Cwordend:
  1940.     {
  1941.         if (text == textstart)
  1942.             goto fail;
  1943.         if (!(SYNTAX(text[-1]) & Sword))
  1944.             goto fail;
  1945.         if (text == textend)
  1946.             goto continue_matching;
  1947.         if (!(SYNTAX(*text) & Sword))
  1948.                 goto continue_matching;
  1949.                 goto fail;
  1950.     }
  1951.     case Cwordbound:
  1952.     {
  1953.         /* Note: as in gnu regexp, this also matches at the
  1954.          * beginning and end of buffer.  */
  1955.  
  1956.         if (text == textstart || text == textend)
  1957.             goto continue_matching;
  1958.         if ((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword))
  1959.             goto continue_matching;
  1960.         goto fail;
  1961.     }
  1962.     case Cnotwordbound:
  1963.     {
  1964.         /* Note: as in gnu regexp, this never matches at the
  1965.          * beginning and end of buffer.  */
  1966.         if (text == textstart || text == textend)
  1967.             goto fail;
  1968.         if (!((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword)))
  1969.                       goto continue_matching;
  1970.         goto fail;
  1971.     }
  1972.     case Csyntaxspec:
  1973.     {
  1974.         NEXTCHAR(ch);
  1975.         if (!(SYNTAX(ch) & (unsigned char)*code++))
  1976.             goto fail;
  1977.         goto continue_matching;
  1978.     }
  1979.     case Cnotsyntaxspec:
  1980.     {
  1981.         NEXTCHAR(ch);
  1982.         if (SYNTAX(ch) & (unsigned char)*code++)
  1983.             goto fail;
  1984.         goto continue_matching;
  1985.     }
  1986.     default:
  1987.     {
  1988.             FREE_STATE(state);
  1989.             PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");
  1990.         return -2;
  1991.         /*NOTREACHED*/
  1992.     }
  1993.     }
  1994.     
  1995.     
  1996.  
  1997. #if 0 /* This line is never reached --Guido */
  1998.     abort();
  1999. #endif
  2000.     /*
  2001.      *NOTREACHED
  2002.      */
  2003.  
  2004.     /* Using "break;" in the above switch statement is equivalent to "goto fail;" */
  2005.   fail:
  2006.     POP_FAILURE(state, code, text, goto done_matching, goto error);
  2007.     goto continue_matching;
  2008.   
  2009.   done_matching:
  2010. /*   if(translated != NULL) */
  2011. /*      free(translated); */
  2012.     FREE_STATE(state);
  2013.     return -1;
  2014.  
  2015.   error:
  2016. /*   if (translated != NULL) */
  2017. /*      free(translated); */
  2018.     FREE_STATE(state);
  2019.     return -2;
  2020. }
  2021.     
  2022.  
  2023. #undef PREFETCH
  2024. #undef NEXTCHAR
  2025.  
  2026. int re_search(bufp,
  2027.           string,
  2028.           size,
  2029.           pos,
  2030.           range,
  2031.           regs)
  2032.     regexp_t bufp;
  2033.     unsigned char *string;
  2034.     int size;
  2035.     int pos;
  2036.     int range;
  2037.     regexp_registers_t regs;
  2038. {
  2039.     unsigned char *fastmap;
  2040.     unsigned char *translate;
  2041.     unsigned char *text;
  2042.     unsigned char *partstart;
  2043.     unsigned char *partend;
  2044.     int dir;
  2045.     int ret;
  2046.     unsigned char anchor;
  2047.   
  2048.     assert(size >= 0 && pos >= 0);
  2049.     assert(pos + range >= 0 && pos + range <= size); /* Bugfix by ylo */
  2050.   
  2051.     fastmap = bufp->fastmap;
  2052.     translate = bufp->translate;
  2053.     if (fastmap && !bufp->fastmap_accurate) {
  2054.                 re_compile_fastmap(bufp);
  2055.             if (PyErr_Occurred()) return -2;
  2056.     }
  2057.     
  2058.     anchor = bufp->anchor;
  2059.     if (bufp->can_be_null == 1) /* can_be_null == 2: can match null at eob */
  2060.         fastmap = NULL;
  2061.  
  2062.     if (range < 0)
  2063.     {
  2064.         dir = -1;
  2065.         range = -range;
  2066.     }
  2067.     else
  2068.         dir = 1;
  2069.  
  2070.     if (anchor == 2) {
  2071.         if (pos != 0)
  2072.             return -1;
  2073.         else
  2074.             range = 0;
  2075.     }
  2076.  
  2077.     for (; range >= 0; range--, pos += dir)
  2078.     {
  2079.         if (fastmap)
  2080.         {
  2081.             if (dir == 1)
  2082.             { /* searching forwards */
  2083.  
  2084.                 text = string + pos;
  2085.                 partend = string + size;
  2086.                 partstart = text;
  2087.                 if (translate)
  2088.                     while (text != partend &&
  2089.                            !fastmap[(unsigned char) translate[(unsigned char)*text]])
  2090.                         text++;
  2091.                 else
  2092.                     while (text != partend && !fastmap[(unsigned char)*text])
  2093.                         text++;
  2094.                 pos += text - partstart;
  2095.                 range -= text - partstart;
  2096.                 if (pos == size && bufp->can_be_null == 0)
  2097.                     return -1;
  2098.             }
  2099.             else
  2100.             { /* searching backwards */
  2101.                 text = string + pos;
  2102.                 partstart = string + pos - range;
  2103.                 partend = text;
  2104.                 if (translate)
  2105.                     while (text != partstart &&
  2106.                            !fastmap[(unsigned char)
  2107.                                translate[(unsigned char)*text]])
  2108.                         text--;
  2109.                 else
  2110.                     while (text != partstart &&
  2111.                            !fastmap[(unsigned char)*text])
  2112.                         text--;
  2113.                 pos -= partend - text;
  2114.                 range -= partend - text;
  2115.             }
  2116.         }
  2117.         if (anchor == 1)
  2118.         { /* anchored to begline */
  2119.             if (pos > 0 && (string[pos - 1] != '\n'))
  2120.                 continue;
  2121.         }
  2122.         assert(pos >= 0 && pos <= size);
  2123.         ret = re_match(bufp, string, size, pos, regs);
  2124.         if (ret >= 0)
  2125.             return pos;
  2126.         if (ret == -2)
  2127.             return -2;
  2128.     }
  2129.     return -1;
  2130. }
  2131.  
  2132. /*
  2133. ** Local Variables:
  2134. ** mode: c
  2135. ** c-file-style: "python"
  2136. ** End:
  2137. */
  2138.